[BOJ] 5670 휴대폰 자판

vector로 트라이 구현하기

2024.08.01.

0. 들어가기

문제 링크 : https://www.acmicpc.net/problem/5670
정답 코드 : http://boj.kr/a5a13d455d794b6ab68e5ddb68459081

1. 문제 요약

사전에 저장된 영단어의 갯수와 해당 갯수대로 영단어 목록이 주어진다.

단어를 입력할 때, 가능한 다음 글자가 하나 뿐이라면 자동으로 다음 글자가 입력된다.

단, 첫 글자는 항상 사용자가 입력해야 한다.

각 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구한다.

2. 풀이 정리

모든 단어를 트라이에 저장한다.

트라이의 루트 노드에서부터 시작해서 모든 노드를 탐색한다.

인자로는 현재까지 버튼을 누른 횟수 cnt를 넘겨준다.
isEnd = true를 만나면, 전체 버튼을 누른 횟수 totalCnt 변수에 현재까지 버튼을 누른 횟수를 더해준다.
다음 노드가 존재한다면, 해당 노드를 방문한다.
- 현재 글자가 첫 글자가 아니면서, 현재 노드에서 다음 노드를 탐색할 때 단어가 끝나는 경우를 포함해서 경우의 수가 하나밖에 없다면, 다음 노드를 탐색할 때의 비용(자판 입력 횟수)은 0이다. cnt를 증가시키지 않는다.
- 나머지 경우에는 다음 노드를 탐색할 때 cnt를 증가시킨다.

3. 구현

트라이의 각 노드는 bool isEnd, vector<pair<char, node*> > next를 가진다.

isEnd는 현재 노드에서 끝나는 단어가 있는지를 가리킨다.
next는 다음 노드를 가리키는 포인터의 vector 배열이다.
- 트라이를 구현하기 위해서는 node* next[26]처럼 모든 알파벳에 대한 포인터 변수 배열을 만드는 방법도 있다. 하지만 접근 시간이 빠른 대신 메모리가 낭비되고, 이 문제에서는 메모리 초과를 받을 수 있다.
- for (nodePair nextNode : next)처럼 순회하여 next 안에 원하는 문자에 대한 포인터가 있는지 탐색하고, 있다면 해당 포인터의 노드로 이동, 없다면 노드를 하나 생성하고 해당 노드로 이동한다.

전체 코드

#include <iostream>
#include <vector>
#include <string>
#define endl '\n'
#define nodePair pair<char, node*>
using namespace std;

int N;
int totalCnt;

struct node {
	bool isEnd;
	vector<nodePair> next;

	node()
	{
		isEnd = false;
	}

	void insert(string S, int index)
	{
		if (index == S.length())
		{
			isEnd = true;
			return;
		}

		char nextChar = S[index];
		node* nextPtr = NULL;

		for (nodePair nextNode : next)
		{
			if (nextNode.first == nextChar)
				nextPtr = nextNode.second;
		}

		if (nextPtr == NULL)
		{
			nextPtr = new node;;
			next.push_back({ nextChar, nextPtr });
		}
		nextPtr->insert(S, index + 1);
	}

	void find(int cnt)
	{
		int nextCnt = 0;

		if (isEnd)
		{
			nextCnt++;
			totalCnt += cnt;
		}

		for (nodePair nextNode : next)
		{
			if (nextNode.second)
				nextCnt++;
		}

		if (cnt && nextCnt == 1)
		{
			for (nodePair nextNode : next)
			{
				if (nextNode.second)
					nextNode.second->find(cnt);
			}

		}
		else
		{
			for (nodePair nextNode : next)
			{
				if (nextNode.second)
					nextNode.second->find(cnt + 1);
			}
		}
	}
};

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	while (cin >> N)
	{
		node root;
		totalCnt = 0;

		for (int i = 0; i < N; i++)
		{
			string S;
			cin >> S;
			root.insert(S, 0);
		}

		root.find(0);

		cout << fixed;
		cout.precision(2);
		cout << totalCnt / (double)N << endl;
	}

	return 0;
}

4. 여담

트라이 사용한다는 것 까지는 알겠는데, 연결 리스트 만드는 법을 홀랑 까먹어서 검색 좀 했다.
다음 포인터를 배열로 저장했다가 메모리 초과를 받아서 vector로 고쳐줬다. vector로 트라이 짜는 건 처음이었다.

Table Of Contents

0. 들어가기

1. 문제 요약

2. 풀이 정리

3. 구현

4. 여담